|
In computing, the alias method is a family of efficient algorithms for sampling from a discrete probability distribution, due to A. J. Walker. That is, it returns integer values according to some arbitrary probability distribution . The algorithms typically use or preprocessing time, after which random values can be drawn from the distribution in time. ==Operation== Internally, the algorithm consults two tables, a ''probability table'' and an ''alias table'' (for ). To generate a random outcome, a fair die is rolled to determine an index into the two tables. Based on the probability stored at that index, a biased coin is then flipped, and the outcome of the flip is used to choose between a result of and .〔(Darts, Dice, and Coins: Sampling from a Discrete Distribution ). KeithSchwarz.com. Retrieved on 2011-12-27.〕 More concretely, the algorithm operates as follows: # Generate a uniform random variate . # Let and . # If , return . This is the biased coin flip. # Otherwise, return . An alternative formulation of the probability table, proposed by Marsaglia et. al. as the “square histogram” method, uses the condition in the third step (where ) instead of computing . 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Alias method」の詳細全文を読む スポンサード リンク
|